package com.ting.test.algorithms.排序算法;

/**
 * 将数组按照从小到大的方法排列
 * 选择排序：
 * 核心思想 :每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
 * 1.从左到右，将0~i位置的元素依次两两进行比较，如果小则替换，
 * 每遍历一次，会产生局部的最大，最小值，但并不会使得某一个元素的位置确定下来
 * 时间复杂度为O(n^2) 等差数列 a*n^2 +b*n +c
 * 空间复杂度O(1)
 */
public class 插入排序1 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 14, 21, 13, 567, 88, 54, 34, 2, 3};
        int[] result = selectSort(arr);
        System.out.print("arr=[");
        for (int res : arr) {
            System.out.print(res + ",");
        }
        System.out.println("]");

        System.out.print("result=[");
        for (int res : result) {
            System.out.print(res + ",");
        }
        System.out.println("]");
    }

    private static int[] selectSort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j+1);
                }
            }
        }

        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }
}
